#include <iostream>
#include <vector>
#include <limits>

#define INFINITY 1000

using namespace std;

class Graph{
	private:
		vector<vector<int> > weight;  	// informacion de adyacencia
		
	public:
		Graph(){}
		void read(bool directed);
		void floyd();
		void print();
};

int main(){
	Graph g;

	g.read(false);
	g.print();
	cout << endl;
	g.floyd();
	g.print();
	
	return 0;
}

void Graph::read(bool directed){
	int n_nodes, n_edges, x, y, w; 

	cin >> n_nodes >> n_edges;
	
	weight.resize(n_nodes);		
	
	for(int i = 0; i < n_nodes; i++){
		weight[i].assign(n_nodes, INFINITY);
		//weight[i][i] = 0; 
	}
		
	for(int i = 0; i < n_edges; i++) {
		cin >> x >> y >> w;

		weight[x][y] = w;
		
  		if(directed == false){ 
			weight[y][x] = w;		
		}
	}		
}

void Graph::floyd() {
	int through_k;    // distancia a traves del vertice k 

	for (unsigned k = 0; k < weight.size(); k++){
		for (unsigned i = 0; i < weight.size(); i++){
			for (unsigned j = 0; j < weight.size(); j++){
				through_k = weight[i][k] + weight[k][j];
				
				if (through_k < weight[i][j]){
	         	weight[i][j] = through_k;
	         }
			}
		}
	}
}

void Graph::print(){
	for (unsigned i = 0; i < weight.size(); i++) {
		for (unsigned j = 0; j < weight[i].size(); j++){
			if(INFINITY == weight[i][j])
				cout << "* ";
			else
				cout << weight[i][j] << " ";
		}
		cout << endl;
	}
}

